//一、左旋代码分析
/*-----------------------------------------------------------
|   node           right
|   / /    ==>     / /
|   a  right     node  y
|       / /       / /    
|       b  y     a   b    //左旋
-----------------------------------------------------------*/
static rb_node_t* rb_rotate_left(rb_node_t* node, rb_node_t* root)
{
    rb_node_t* right = node->right;    //指定指针指向 right<--node->right
 
    if ((node->right == right->left)) {
        right->left->parent = node;  //好比上面的注释图，node成为b的父母
    }
    right->left = node;   //node成为right的左孩子

    /* 将right放到原来nood的位置：左则左，右则右 */
    if ((right->parent == node->parent)) {
        if (node == node->parent->right) {
            node->parent->right = right;
        } else {
            node->parent->left = right;
        }
    } else {
        root = right;
    }
    node->parent = right;  //right成为node的父母
 
    return root;
}

//二、右旋
/*-----------------------------------------------------------
|       node            left
|       / /             / /
|    left  y   ==>    a    node
|   / /                    / /
|  a   b                  b   y  //右旋与左旋差不多，分析略过
-----------------------------------------------------------*/
static rb_node_t* rb_rotate_right(rb_node_t* node, rb_node_t* root)
{
    rb_node_t* left = node->left;
 
    if ((node->left = left->right))
    {
        left->right->parent = node;
    }
    left->right = node;
 
    if ((left->parent = node->parent))
    {
        if (node == node->parent->right)
        {
            node->parent->right = left;
        }
        else
        {
            node->parent->left = left;
        }
    }
    else
    {
        root = left;
    }
    node->parent = left;
 
    return root;
}